package LinkList;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: LinkList
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-11-02  18:23
 * @Description: TODO
 * @Version: 1.0
 */
public class 扁平化多级双向链表430 {

    class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    }

    public Node flatten(Node head) {
        if (head == null) {
            return null;
        }
        dfs(head);
        return head;
    }

    public Node dfs(Node node) {
        Node cur = node;
        // 记录链表的最后一个节点
        Node last = null;

        while (cur != null) {
            Node next = cur.next;
            //  如果有子节点，那么首先处理子节点
            if (cur.child != null) {
                Node childLast = dfs(cur.child);
                next = cur.next;
                //  将 node 与 child 相连
                cur.next = cur.child;
                cur.child.prev = cur;

                //  如果 next 不为空，就将 last 与 next 相连
                if (next != null) {
                    childLast.next = next;
                    next.prev = childLast;
                }

                // 将 child 置为空
                cur.child = null;
                last = childLast;
            } else {
                last = cur;
            }
            cur = next;
        }
        return last;
    }

    public Node dfs3(Node node) {
        Node curr=node;
        Node last=null;
        while (curr!=null){
            Node next=curr.next;
            if (curr.child!=null){
                Node childLast=dfs3(node.child);
                next=curr.next;
                curr.next=curr.child;
                curr.child.prev=curr;
                if (next!=null){
                    childLast.next=next;
                    next.prev=childLast;
                }
                // 将child 设置null
                curr.child=null;
                last=childLast;
            }else {
                last=curr;
            }
            curr=next;
        }
        return last;
    }
}
